home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / flex_247.zip / flex_247 / tblcmp.c < prev    next >
C/C++ Source or Header  |  1993-12-07  |  24KB  |  889 lines
  1. /* tblcmp - table compression routines */
  2.  
  3. /*-
  4.  * Copyright (c) 1990 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant
  11.  * to contract no. DE-AC03-76SF00098 between the United States
  12.  * Department of Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted provided
  15.  * that: (1) source distributions retain this entire copyright notice and
  16.  * comment, and (2) distributions including binaries display the following
  17.  * acknowledgement:  ``This product includes software developed by the
  18.  * University of California, Berkeley and its contributors'' in the
  19.  * documentation or other materials provided with the distribution and in
  20.  * all advertising materials mentioning features or use of this software.
  21.  * Neither the name of the University nor the names of its contributors may
  22.  * be used to endorse or promote products derived from this software without
  23.  * specific prior written permission.
  24.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  25.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  26.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27.  */
  28.  
  29. /* $Header: /home/daffy/u0/vern/flex/RCS/tblcmp.c,v 2.10 93/12/07 10:18:30 vern Exp $ */
  30.  
  31. #include "flexdef.h"
  32.  
  33.  
  34. /* declarations for functions that have forward references */
  35.  
  36. void mkentry PROTO((register int*, int, int, int, int));
  37. void mkprot PROTO((int[], int, int));
  38. void mktemplate PROTO((int[], int, int));
  39. void mv2front PROTO((int));
  40. int tbldiff PROTO((int[], int, int[]));
  41.  
  42.  
  43. /* bldtbl - build table entries for dfa state
  44.  *
  45.  * synopsis
  46.  *   int state[numecs], statenum, totaltrans, comstate, comfreq;
  47.  *   bldtbl( state, statenum, totaltrans, comstate, comfreq );
  48.  *
  49.  * State is the statenum'th dfa state.  It is indexed by equivalence class and
  50.  * gives the number of the state to enter for a given equivalence class.
  51.  * totaltrans is the total number of transitions out of the state.  Comstate
  52.  * is that state which is the destination of the most transitions out of State.
  53.  * Comfreq is how many transitions there are out of State to Comstate.
  54.  *
  55.  * A note on terminology:
  56.  *    "protos" are transition tables which have a high probability of
  57.  * either being redundant (a state processed later will have an identical
  58.  * transition table) or nearly redundant (a state processed later will have
  59.  * many of the same out-transitions).  A "most recently used" queue of
  60.  * protos is kept around with the hope that most states will find a proto
  61.  * which is similar enough to be usable, and therefore compacting the
  62.  * output tables.
  63.  *    "templates" are a special type of proto.  If a transition table is
  64.  * homogeneous or nearly homogeneous (all transitions go to the same
  65.  * destination) then the odds are good that future states will also go
  66.  * to the same destination state on basically the same character set.
  67.  * These homogeneous states are so common when dealing with large rule
  68.  * sets that they merit special attention.  If the transition table were
  69.  * simply made into a proto, then (typically) each subsequent, similar
  70.  * state will differ from the proto for two out-transitions.  One of these
  71.  * out-transitions will be that character on which the proto does not go
  72.  * to the common destination, and one will be that character on which the
  73.  * state does not go to the common destination.  Templates, on the other
  74.  * hand, go to the common state on EVERY transition character, and therefore
  75.  * cost only one difference.
  76.  */
  77.  
  78. void bldtbl( state, statenum, totaltrans, comstate, comfreq )
  79. int state[], statenum, totaltrans, comstate, comfreq;
  80.     {
  81.     int extptr, extrct[2][CSIZE + 1];
  82.     int mindiff, minprot, i, d;
  83.  
  84.     /* If extptr is 0 then the first array of extrct holds the result
  85.      * of the "best difference" to date, which is those transitions
  86.      * which occur in "state" but not in the proto which, to date,
  87.      * has the fewest differences between itself and "state".  If
  88.      * extptr is 1 then the second array of extrct hold the best
  89.      * difference.  The two arrays are toggled between so that the
  90.      * best difference to date can be kept around and also a difference
  91.      * just created by checking against a candidate "best" proto.
  92.      */
  93.  
  94.     extptr = 0;
  95.  
  96.     /* If the state has too few out-transitions, don't bother trying to
  97.      * compact its tables.
  98.      */
  99.  
  100.     if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
  101.         mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  102.  
  103.     else
  104.         {
  105.         /* "checkcom" is true if we should only check "state" against
  106.          * protos which have the same "comstate" value.
  107.          */
  108.         int checkcom =
  109.             comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
  110.  
  111.         minprot = firstprot;
  112.         mindiff = totaltrans;
  113.  
  114.         if ( checkcom )
  115.             {
  116.             /* Find first proto which has the same "comstate". */
  117.             for ( i = firstprot; i != NIL; i = protnext[i] )
  118.                 if ( protcomst[i] == comstate )
  119.                     {
  120.                     minprot = i;
  121.                     mindiff = tbldiff( state, minprot,
  122.                             extrct[extptr] );
  123.                     break;
  124.                     }
  125.             }
  126.  
  127.         else
  128.             {
  129.             /* Since we've decided that the most common destination
  130.              * out of "state" does not occur with a high enough
  131.              * frequency, we set the "comstate" to zero, assuring
  132.              * that if this state is entered into the proto list,
  133.              * it will not be considered a template.
  134.              */
  135.             comstate = 0;
  136.  
  137.             if ( firstprot != NIL )
  138.                 {
  139.                 minprot = firstprot;
  140.                 mindiff = tbldiff( state, minprot,
  141.                         extrct[extptr] );
  142.                 }
  143.             }
  144.  
  145.         /* We now have the first interesting proto in "minprot".  If
  146.          * it matches within the tolerances set for the first proto,
  147.          * we don't want to bother scanning the rest of the proto list
  148.          * to see if we have any other reasonable matches.
  149.          */
  150.  
  151.         if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
  152.             {
  153.             /* Not a good enough match.  Scan the rest of the
  154.              * protos.
  155.              */
  156.             for ( i = minprot; i != NIL; i = protnext[i] )
  157.                 {
  158.                 d = tbldiff( state, i, extrct[1 - extptr] );
  159.                 if ( d < mindiff )
  160.                     {
  161.                     extptr = 1 - extptr;
  162.                     mindiff = d;
  163.                     minprot = i;
  164.                     }
  165.                 }
  166.             }
  167.  
  168.         /* Check if the proto we've decided on as our best bet is close
  169.          * enough to the state we want to match to be usable.
  170.          */
  171.  
  172.         if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
  173.             {
  174.             /* No good.  If the state is homogeneous enough,
  175.              * we make a template out of it.  Otherwise, we
  176.              * make a proto.
  177.              */
  178.  
  179.             if ( comfreq * 100 >=
  180.                  totaltrans * TEMPLATE_SAME_PERCENTAGE )
  181.                 mktemplate( state, statenum, comstate );
  182.  
  183.             else
  184.                 {
  185.                 mkprot( state, statenum, comstate );
  186.                 mkentry( state, numecs, statenum,
  187.                     JAMSTATE, totaltrans );
  188.                 }
  189.             }
  190.  
  191.         else
  192.             { /* use the proto */
  193.             mkentry( extrct[extptr], numecs, statenum,
  194.                 prottbl[minprot], mindiff );
  195.  
  196.             /* If this state was sufficiently different from the
  197.              * proto we built it from, make it, too, a proto.
  198.              */
  199.  
  200.             if ( mindiff * 100 >=
  201.                  totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
  202.                 mkprot( state, statenum, comstate );
  203.  
  204.             /* Since mkprot added a new proto to the proto queue,
  205.              * it's possible that "minprot" is no longer on the
  206.              * proto queue (if it happened to have been the last
  207.              * entry, it would have been bumped off).  If it's
  208.              * not there, then the new proto took its physical
  209.              * place (though logically the new proto is at the
  210.              * beginning of the queue), so in that case the
  211.              * following call will do nothing.
  212.              */
  213.  
  214.             mv2front( minprot );
  215.             }
  216.         }
  217.     }
  218.  
  219.  
  220. /* cmptmps - compress template table entries
  221.  *
  222.  * Template tables are compressed by using the 'template equivalence
  223.  * classes', which are collections of transition character equivalence
  224.  * classes which always appear together in templates - really meta-equivalence
  225.  * classes.
  226.  */
  227.  
  228. void cmptmps()
  229.     {
  230.     int tmpstorage[CSIZE + 1];
  231.     register int *tmp = tmpstorage, i, j;
  232.     int totaltrans, trans;
  233.  
  234.     peakpairs = numtemps * numecs + tblend;
  235.  
  236.     if ( usemecs )
  237.         {
  238.         /* Create equivalence classes based on data gathered on
  239.          * template transitions.
  240.          */
  241.         nummecs = cre8ecs( tecfwd, tecbck, numecs );
  242.         }
  243.  
  244.     else
  245.         nummecs = numecs;
  246.  
  247.     while ( lastdfa + numtemps + 1 >= current_max_dfas )
  248.         increase_max_dfas();
  249.  
  250.     /* Loop through each template. */
  251.  
  252.     for ( i = 1; i <= numtemps; ++i )
  253.         {
  254.         /* Number of non-jam transitions out of this template. */
  255.         totaltrans = 0;
  256.  
  257.         for ( j = 1; j <= numecs; ++j )
  258.             {
  259.             trans = tnxt[numecs * i + j];
  260.  
  261.             if ( usemecs )
  262.                 {
  263.                 /* The absolute value of tecbck is the
  264.                  * meta-equivalence class of a given
  265.                  * equivalence class, as set up by cre8ecs().
  266.                  */
  267.                 if ( tecbck[j] > 0 )
  268.                     {
  269.                     tmp[tecbck[j]] = trans;
  270.  
  271.                     if ( trans > 0 )
  272.                         ++totaltrans;
  273.                     }
  274.                 }
  275.  
  276.             else
  277.                 {
  278.                 tmp[j] = trans;
  279.  
  280.                 if ( trans > 0 )
  281.                     ++totaltrans;
  282.                 }
  283.             }
  284.  
  285.         /* It is assumed (in a rather subtle way) in the skeleton
  286.          * that if we're using meta-equivalence classes, the def[]
  287.          * entry for all templates is the jam template, i.e.,
  288.          * templates never default to other non-jam table entries
  289.          * (e.g., another template)
  290.          */
  291.  
  292.         /* Leave room for the jam-state after the last real state. */
  293.         mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );
  294.         }
  295.     }
  296.  
  297.  
  298.  
  299. /* expand_nxt_chk - expand the next check arrays */
  300.  
  301. void expand_nxt_chk()
  302.     {
  303.     register int old_max = current_max_xpairs;
  304.  
  305.     current_max_xpairs += MAX_XPAIRS_INCREMENT;
  306.  
  307.     ++num_reallocs;
  308.  
  309.     nxt = reallocate_integer_array( nxt, current_max_xpairs );
  310.     chk = reallocate_integer_array( chk, current_max_xpairs );
  311.  
  312.     zero_out( (char *) (chk + old_max),
  313.         MAX_XPAIRS_INCREMENT * sizeof( int ) / sizeof( char ) );
  314.     }
  315.  
  316.  
  317. /* find_table_space - finds a space in the table for a state to be placed
  318.  *
  319.  * synopsis
  320.  *     int *state, numtrans, block_start;
  321.  *     int find_table_space();
  322.  *
  323.  *     block_start = find_table_space( state, numtrans );
  324.  *
  325.  * State is the state to be added to the full speed transition table.
  326.  * Numtrans is the number of out-transitions for the state.
  327.  *
  328.  * find_table_space() returns the position of the start of the first block (in
  329.  * chk) able to accommodate the state
  330.  *
  331.  * In determining if a state will or will not fit, find_table_space() must take
  332.  * into account the fact that an end-of-buffer state will be added at [0],
  333.  * and an action number will be added in [-1].
  334.  */
  335.  
  336. int find_table_space( state, numtrans )
  337. int *state, numtrans;
  338.     {
  339.     /* Firstfree is the position of the first possible occurrence of two
  340.      * consecutive unused records in the chk and nxt arrays.
  341.      */
  342.     register int i;
  343.     register int *state_ptr, *chk_ptr;
  344.     register int *ptr_to_last_entry_in_state;
  345.  
  346.     /* If there are too many out-transitions, put the state at the end of
  347.      * nxt and chk.
  348.      */
  349.     if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT )
  350.         {
  351.         /* If table is empty, return the first available spot in
  352.          * chk/nxt, which should be 1.
  353.          */
  354.         if ( tblend < 2 )
  355.             return 1;
  356.  
  357.         /* Start searching for table space near the end of
  358.          * chk/nxt arrays.
  359.          */
  360.         i = tblend - numecs;
  361.         }
  362.  
  363.     else
  364.         /* Start searching for table space from the beginning
  365.          * (skipping only the elements which will definitely not
  366.          * hold the new state).
  367.          */
  368.         i = firstfree;
  369.  
  370.     while ( 1 )    /* loops until a space is found */
  371.         {
  372.         while ( i + numecs >= current_max_xpairs )
  373.             expand_nxt_chk();
  374.  
  375.         /* Loops until space for end-of-buffer and action number
  376.          * are found.
  377.          */
  378.         while ( 1 )
  379.             {
  380.             /* Check for action number space. */
  381.             if ( chk[i - 1] == 0 )
  382.                 {
  383.                 /* Check for end-of-buffer space. */
  384.                 if ( chk[i] == 0 )
  385.                     break;
  386.  
  387.                 else
  388.                     /* Since i != 0, there is no use
  389.                      * checking to see if (++i) - 1 == 0,
  390.                      * because that's the same as i == 0,
  391.                      * so we skip a space.
  392.                      */
  393.                     i += 2;
  394.                 }
  395.  
  396.             else
  397.                 ++i;
  398.  
  399.             while ( i + numecs >= current_max_xpairs )
  400.                 expand_nxt_chk();
  401.             }
  402.  
  403.         /* If we started search from the beginning, store the new
  404.          * firstfree for the next call of find_table_space().
  405.          */
  406.         if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT )
  407.             firstfree = i + 1;
  408.  
  409.         /* Check to see if all elements in chk (and therefore nxt)
  410.          * that are needed for the new state have not yet been taken.
  411.          */
  412.  
  413.         state_ptr = &state[1];
  414.         ptr_to_last_entry_in_state = &chk[i + numecs + 1];
  415.  
  416.         for ( chk_ptr = &chk[i + 1];
  417.               chk_ptr != ptr_to_last_entry_in_state; ++chk_ptr )
  418.             if ( *(state_ptr++) != 0 && *chk_ptr != 0 )
  419.                 break;
  420.  
  421.         if ( chk_ptr == ptr_to_last_entry_in_state )
  422.             return i;
  423.  
  424.         else
  425.         ++i;
  426.         }
  427.     }
  428.  
  429.  
  430. /* inittbl - initialize transition tables
  431.  *
  432.  * Initializes "firstfree" to be one beyond the end of the table.  Initializes
  433.  * all "chk" entries to be zero.
  434.  */
  435. void inittbl()
  436.     {
  437.     register int i;
  438.  
  439.     zero_out( (char *) chk,
  440.         current_max_xpairs * sizeof( int ) / sizeof( char ) );
  441.  
  442.     tblend = 0;
  443.     firstfree = tblend + 1;
  444.     numtemps = 0;
  445.  
  446.     if ( usemecs )
  447.         {
  448.         /* Set up doubly-linked meta-equivalence classes; these
  449.          * are sets of equivalence classes which all have identical
  450.          * transitions out of TEMPLATES.
  451.          */
  452.  
  453.         tecbck[1] = NIL;
  454.  
  455.         for ( i = 2; i <= numecs; ++i )
  456.             {
  457.             tecbck[i] = i - 1;
  458.             tecfwd[i - 1] = i;
  459.             }
  460.  
  461.         tecfwd[numecs] = NIL;
  462.         }
  463.     }
  464.  
  465.  
  466. /* mkdeftbl - make the default, "jam" table entries */
  467.  
  468. void mkdeftbl()
  469.     {
  470.     int i;
  471.  
  472.     jamstate = lastdfa + 1;
  473.  
  474.     ++tblend; /* room for transition on end-of-buffer character */
  475.  
  476.     while ( tblend + numecs >= current_max_xpairs )
  477.         expand_nxt_chk();
  478.  
  479.     /* Add in default end-of-buffer transition. */
  480.     nxt[tblend] = end_of_buffer_state;
  481.     chk[tblend] = jamstate;
  482.  
  483.     for ( i = 1; i <= numecs; ++i )
  484.         {
  485.         nxt[tblend + i] = 0;
  486.         chk[tblend + i] = jamstate;
  487.         }
  488.  
  489.     jambase = tblend;
  490.  
  491.     base[jamstate] = jambase;
  492.     def[jamstate] = 0;
  493.  
  494.     tblend += numecs;
  495.     ++numtemps;
  496.     }
  497.  
  498.  
  499. /* mkentry - create base/def and nxt/chk entries for transition array
  500.  *
  501.  * synopsis
  502.  *   int state[numchars + 1], numchars, statenum, deflink, totaltrans;
  503.  *   mkentry( state, numchars, statenum, deflink, totaltrans );
  504.  *
  505.  * "state" is a transition array "numchars" characters in size, "statenum"
  506.  * is the offset to be used into the base/def tables, and "deflink" is the
  507.  * entry to put in the "def" table entry.  If "deflink" is equal to
  508.  * "JAMSTATE", then no attempt will be made to fit zero entries of "state"
  509.  * (i.e., jam entries) into the table.  It is assumed that by linking to
  510.  * "JAMSTATE" they will be taken care of.  In any case, entries in "state"
  511.  * marking transitions to "SAME_TRANS" are treated as though they will be
  512.  * taken care of by whereever "deflink" points.  "totaltrans" is the total
  513.  * number of transitions out of the state.  If it is below a certain threshold,
  514.  * the tables are searched for an interior spot that will accommodate the
  515.  * state array.
  516.  */
  517.  
  518. void mkentry( state, numchars, statenum, deflink, totaltrans )
  519. register int *state;
  520. int numchars, statenum, deflink, totaltrans;
  521.     {
  522.     register int minec, maxec, i, baseaddr;
  523.     int tblbase, tbllast;
  524.  
  525.     if ( totaltrans == 0 )
  526.         { /* there are no out-transitions */
  527.         if ( deflink == JAMSTATE )
  528.             base[statenum] = JAMSTATE;
  529.         else
  530.             base[statenum] = 0;
  531.  
  532.         def[statenum] = deflink;
  533.         return;
  534.         }
  535.  
  536.     for ( minec = 1; minec <= numchars; ++minec )
  537.         {
  538.         if ( state[minec] != SAME_TRANS )
  539.             if ( state[minec] != 0 || deflink != JAMSTATE )
  540.                 break;
  541.         }
  542.  
  543.     if ( totaltrans == 1 )
  544.         {
  545.         /* There's only one out-transition.  Save it for later to fill
  546.          * in holes in the tables.
  547.          */
  548.         stack1( statenum, minec, state[minec], deflink );
  549.         return;
  550.         }
  551.  
  552.     for ( maxec = numchars; maxec > 0; --maxec )
  553.         {
  554.         if ( state[maxec] != SAME_TRANS )
  555.             if ( state[maxec] != 0 || deflink != JAMSTATE )
  556.                 break;
  557.         }
  558.  
  559.     /* Whether we try to fit the state table in the middle of the table
  560.      * entries we have already generated, or if we just take the state
  561.      * table at the end of the nxt/chk tables, we must make sure that we
  562.      * have a valid base address (i.e., non-negative).  Note that
  563.      * negative base addresses dangerous at run-time (because indexing
  564.      * the nxt array with one and a low-valued character will access
  565.      * memory before the start of the array.
  566.      */
  567.  
  568.     /* Find the first transition of state that we need to worry about. */
  569.     if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )
  570.         {
  571.         /* Attempt to squeeze it into the middle of the tables. */
  572.         baseaddr = firstfree;
  573.  
  574.         while ( baseaddr < minec )
  575.             {
  576.             /* Using baseaddr would result in a negative base
  577.              * address below; find the next free slot.
  578.              */
  579.             for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )
  580.                 ;
  581.             }
  582.  
  583.         while ( baseaddr + maxec - minec + 1 >= current_max_xpairs )
  584.             expand_nxt_chk();
  585.  
  586.         for ( i = minec; i <= maxec; ++i )
  587.             if ( state[i] != SAME_TRANS &&
  588.                  (state[i] != 0 || deflink != JAMSTATE) &&
  589.                  chk[baseaddr + i - minec] != 0 )
  590.                 { /* baseaddr unsuitable - find another */
  591.                 for ( ++baseaddr;
  592.                       baseaddr < current_max_xpairs &&
  593.                       chk[baseaddr] != 0; ++baseaddr )
  594.                     ;
  595.  
  596.                 while ( baseaddr + maxec - minec + 1 >=
  597.                     current_max_xpairs )
  598.                     expand_nxt_chk();
  599.  
  600.                 /* Reset the loop counter so we'll start all
  601.                  * over again next time it's incremented.
  602.                  */
  603.  
  604.                 i = minec - 1;
  605.                 }
  606.         }
  607.  
  608.     else
  609.         {
  610.         /* Ensure that the base address we eventually generate is
  611.          * non-negative.
  612.          */
  613.         baseaddr = MAX( tblend + 1, minec );
  614.         }
  615.  
  616.     tblbase = baseaddr - minec;
  617.     tbllast = tblbase + maxec;
  618.  
  619.     while ( tbllast + 1 >= current_max_xpairs )
  620.         expand_nxt_chk();
  621.  
  622.     base[statenum] = tblbase;
  623.     def[statenum] = deflink;
  624.  
  625.     for ( i = minec; i <= maxec; ++i )
  626.         if ( state[i] != SAME_TRANS )
  627.             if ( state[i] != 0 || deflink != JAMSTATE )
  628.                 {
  629.                 nxt[tblbase + i] = state[i];
  630.                 chk[tblbase + i] = statenum;
  631.                 }
  632.  
  633.     if ( baseaddr == firstfree )
  634.         /* Find next free slot in tables. */
  635.         for ( ++firstfree; chk[firstfree] != 0; ++firstfree )
  636.             ;
  637.  
  638.     tblend = MAX( tblend, tbllast );
  639.     }
  640.  
  641.  
  642. /* mk1tbl - create table entries for a state (or state fragment) which
  643.  *            has only one out-transition
  644.  */
  645.  
  646. void mk1tbl( state, sym, onenxt, onedef )
  647. int state, sym, onenxt, onedef;
  648.     {
  649.     if ( firstfree < sym )
  650.         firstfree = sym;
  651.  
  652.     while ( chk[firstfree] != 0 )
  653.         if ( ++firstfree >= current_max_xpairs )
  654.             expand_nxt_chk();
  655.  
  656.     base[state] = firstfree - sym;
  657.     def[state] = onedef;
  658.     chk[firstfree] = state;
  659.     nxt[firstfree] = onenxt;
  660.  
  661.     if ( firstfree > tblend )
  662.         {
  663.         tblend = firstfree++;
  664.  
  665.         if ( firstfree >= current_max_xpairs )
  666.             expand_nxt_chk();
  667.         }
  668.     }
  669.  
  670.  
  671. /* mkprot - create new proto entry */
  672.  
  673. void mkprot( state, statenum, comstate )
  674. int state[], statenum, comstate;
  675.     {
  676.     int i, slot, tblbase;
  677.  
  678.     if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )
  679.         {
  680.         /* Gotta make room for the new proto by dropping last entry in
  681.          * the queue.
  682.          */
  683.         slot = lastprot;
  684.         lastprot = protprev[lastprot];
  685.         protnext[lastprot] = NIL;
  686.         }
  687.  
  688.     else
  689.         slot = numprots;
  690.  
  691.     protnext[slot] = firstprot;
  692.  
  693.     if ( firstprot != NIL )
  694.         protprev[firstprot] = slot;
  695.  
  696.     firstprot = slot;
  697.     prottbl[slot] = statenum;
  698.     protcomst[slot] = comstate;
  699.  
  700.     /* Copy state into save area so it can be compared with rapidly. */
  701.     tblbase = numecs * (slot - 1);
  702.  
  703.     for ( i = 1; i <= numecs; ++i )
  704.         protsave[tblbase + i] = state[i];
  705.     }
  706.  
  707.  
  708. /* mktemplate - create a template entry based on a state, and connect the state
  709.  *              to it
  710.  */
  711.  
  712. void mktemplate( state, statenum, comstate )
  713. int state[], statenum, comstate;
  714.     {
  715.     int i, numdiff, tmpbase, tmp[CSIZE + 1];
  716.     Char transset[CSIZE + 1];
  717.     int tsptr;
  718.  
  719.     ++numtemps;
  720.  
  721.     tsptr = 0;
  722.  
  723.     /* Calculate where we will temporarily store the transition table
  724.      * of the template in the tnxt[] array.  The final transition table
  725.      * gets created by cmptmps().
  726.      */
  727.  
  728.     tmpbase = numtemps * numecs;
  729.  
  730.     if ( tmpbase + numecs >= current_max_template_xpairs )
  731.         {
  732.         current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;
  733.  
  734.         ++num_reallocs;
  735.  
  736.         tnxt = reallocate_integer_array( tnxt,
  737.             current_max_template_xpairs );
  738.         }
  739.  
  740.     for ( i = 1; i <= numecs; ++i )
  741.         if ( state[i] == 0 )
  742.             tnxt[tmpbase + i] = 0;
  743.         else
  744.             {
  745.             transset[tsptr++] = i;
  746.             tnxt[tmpbase + i] = comstate;
  747.             }
  748.  
  749.     if ( usemecs )
  750.         mkeccl( transset, tsptr, tecfwd, tecbck, numecs, 0 );
  751.  
  752.     mkprot( tnxt + tmpbase, -numtemps, comstate );
  753.  
  754.     /* We rely on the fact that mkprot adds things to the beginning
  755.      * of the proto queue.
  756.      */
  757.  
  758.     numdiff = tbldiff( state, firstprot, tmp );
  759.     mkentry( tmp, numecs, statenum, -numtemps, numdiff );
  760.     }
  761.  
  762.  
  763. /* mv2front - move proto queue element to front of queue */
  764.  
  765. void mv2front( qelm )
  766. int qelm;
  767.     {
  768.     if ( firstprot != qelm )
  769.         {
  770.         if ( qelm == lastprot )
  771.             lastprot = protprev[lastprot];
  772.  
  773.         protnext[protprev[qelm]] = protnext[qelm];
  774.  
  775.         if ( protnext[qelm] != NIL )
  776.             protprev[protnext[qelm]] = protprev[qelm];
  777.  
  778.         protprev[qelm] = NIL;
  779.         protnext[qelm] = firstprot;
  780.         protprev[firstprot] = qelm;
  781.         firstprot = qelm;
  782.         }
  783.     }
  784.  
  785.  
  786. /* place_state - place a state into full speed transition table
  787.  *
  788.  * State is the statenum'th state.  It is indexed by equivalence class and
  789.  * gives the number of the state to enter for a given equivalence class.
  790.  * Transnum is the number of out-transitions for the state.
  791.  */
  792.  
  793. void place_state( state, statenum, transnum )
  794. int *state, statenum, transnum;
  795.     {
  796.     register int i;
  797.     register int *state_ptr;
  798.     int position = find_table_space( state, transnum );
  799.  
  800.     /* "base" is the table of start positions. */
  801.     base[statenum] = position;
  802.  
  803.     /* Put in action number marker; this non-zero number makes sure that
  804.      * find_table_space() knows that this position in chk/nxt is taken
  805.      * and should not be used for another accepting number in another
  806.      * state.
  807.      */
  808.     chk[position - 1] = 1;
  809.  
  810.     /* Put in end-of-buffer marker; this is for the same purposes as
  811.      * above.
  812.      */
  813.     chk[position] = 1;
  814.  
  815.     /* Place the state into chk and nxt. */
  816.     state_ptr = &state[1];
  817.  
  818.     for ( i = 1; i <= numecs; ++i, ++state_ptr )
  819.         if ( *state_ptr != 0 )
  820.             {
  821.             chk[position + i] = i;
  822.             nxt[position + i] = *state_ptr;
  823.             }
  824.  
  825.     if ( position + numecs > tblend )
  826.         tblend = position + numecs;
  827.     }
  828.  
  829.  
  830. /* stack1 - save states with only one out-transition to be processed later
  831.  *
  832.  * If there's room for another state on the "one-transition" stack, the
  833.  * state is pushed onto it, to be processed later by mk1tbl.  If there's
  834.  * no room, we process the sucker right now.
  835.  */
  836.  
  837. void stack1( statenum, sym, nextstate, deflink )
  838. int statenum, sym, nextstate, deflink;
  839.     {
  840.     if ( onesp >= ONE_STACK_SIZE - 1 )
  841.         mk1tbl( statenum, sym, nextstate, deflink );
  842.  
  843.     else
  844.         {
  845.         ++onesp;
  846.         onestate[onesp] = statenum;
  847.         onesym[onesp] = sym;
  848.         onenext[onesp] = nextstate;
  849.         onedef[onesp] = deflink;
  850.         }
  851.     }
  852.  
  853.  
  854. /* tbldiff - compute differences between two state tables
  855.  *
  856.  * "state" is the state array which is to be extracted from the pr'th
  857.  * proto.  "pr" is both the number of the proto we are extracting from
  858.  * and an index into the save area where we can find the proto's complete
  859.  * state table.  Each entry in "state" which differs from the corresponding
  860.  * entry of "pr" will appear in "ext".
  861.  *
  862.  * Entries which are the same in both "state" and "pr" will be marked
  863.  * as transitions to "SAME_TRANS" in "ext".  The total number of differences
  864.  * between "state" and "pr" is returned as function value.  Note that this
  865.  * number is "numecs" minus the number of "SAME_TRANS" entries in "ext".
  866.  */
  867.  
  868. int tbldiff( state, pr, ext )
  869. int state[], pr, ext[];
  870.     {
  871.     register int i, *sp = state, *ep = ext, *protp;
  872.     register int numdiff = 0;
  873.  
  874.     protp = &protsave[numecs * (pr - 1)];
  875.  
  876.     for ( i = numecs; i > 0; --i )
  877.         {
  878.         if ( *++protp == *++sp )
  879.             *++ep = SAME_TRANS;
  880.         else
  881.             {
  882.             *++ep = *sp;
  883.             ++numdiff;
  884.             }
  885.         }
  886.  
  887.     return numdiff;
  888.     }
  889.